//因为nums只包含 (n + 1) 个数，且数组的大小为n
//那么，可以用找位置的思路，每个数字的位置（数组下标）就是 (num - 1)
//遍历数组，如果发现一个数字位置不对，就将其和正确位置的数字进行交换
    //如果正确位置的数字等于现在遍历到的数，那么重复数就是这个数
    //如果遍历完数组都还没找到，重复数就是数组最后一个数
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        for (int left = 0; left < n; ++left)
        {
            int index = nums[left] - 1;  //正确位置

            //如果当前位置不是正确位置
            //循环，使得数字找到正确位置
            //必须是循环，因为交换完后，left位置的数可能还不是在正确位置上，必须还要继续交换
            while (left != index)  
            {
                if (nums[left] == nums[index])
                    return nums[left];
                else
                    swap(nums[left], nums[index]);

                index = nums[left] - 1;
            }
        }

        return nums[n - 1];
    }
};